package com.chao.stucture.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author : Rookie
 * @description :
 * @date : 2023/9/25
 */
public class BinaryTreeUtil {

    public static TreeNode buildTree(int []arr) {
        if (arr.length == 0) {
            return null;
        }

        TreeNode rootNode = new TreeNode(arr[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(rootNode);
        int i = 1;
        while (!queue.isEmpty() && i<arr.length) {
            TreeNode currNode = queue.poll();
            if (arr[i] != -1) {
                currNode.left = new TreeNode(arr[i]);
                queue.offer(currNode.left);
            }
            i++;

            if (arr[i]!=-1 && i<arr.length) {
                currNode.right = new TreeNode(arr[i]);
                queue.offer(currNode.right);
            }
            i++;
        }
        return rootNode;
    }

    public interface Traversal {

        /**
         * 层序遍历
         * @param root
         */
        static void sequenceTraversal(TreeNode root) {
            if (root == null) {
                return;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode curr = queue.poll();
                System.out.print(curr.element + " ");
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
        }

        /**
         * 先序遍历
         * @param root
         */
        void preorderTraversal(TreeNode root);

        /**
         * 中序遍历
         * @param root
         */
        void inorderTraversal(TreeNode root);

        /**
         * 后续遍历
         * @param root
         */
        void postorderTraversal(TreeNode root);
    }

    /**
     * 递归遍历
     */
    public static class RecursiveTraversal implements Traversal {


        @Override
        public void preorderTraversal(TreeNode root) {
            if (root == null) {
                return;
            }
            System.out.print(root.element + " ");
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }

        @Override
        public void inorderTraversal(TreeNode root) {
            if (root == null) {
                return;
            }
            inorderTraversal(root.left);
            System.out.print(root.element+" ");
            inorderTraversal(root.right);
        }

        @Override
        public void postorderTraversal(TreeNode root) {
            if (root == null) {
                return;
            }
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            System.out.print(root.element + " ");
        }
    }

    /**
     * 迭代遍历
     */
    public static class IterativeTraversal implements Traversal {


        @Override
        public void preorderTraversal(TreeNode root) {
            if (root == null) {
                return;
            }
            Stack<TreeNode> stack = new Stack<>();
            TreeNode curr = root;

            while (!stack.isEmpty() || curr != null) {
                if (curr != null) {
                    stack.push(curr);
                    System.out.print(curr.element + " ");
                    curr = curr.left;
                } else {
                    curr = stack.pop();
                    curr = curr.right;
                }
            }
        }

        @Override
        public void inorderTraversal(TreeNode root) {
            if (root == null) {
                return;
            }
            Stack<TreeNode> stack = new Stack<>();
            TreeNode curr = root;

            while (!stack.isEmpty() || curr != null) {
                if (curr != null) {
                    stack.push(curr);
                    curr = curr.left;
                } else {
                    curr = stack.pop();
                    System.out.print(curr.element + " ");
                    curr = curr.right;
                }
            }
        }

        @Override
        public void postorderTraversal(TreeNode root) {

        }
    }
}
